package com.gorkr.labuladong.data_struct.merge_sort;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @author gorkr
 * @date 2022/05/30 09:42
 **/
public class QuickSort {
    public void quickSort(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        shuffle(nums);
        sort(nums, lo, hi);
    }


    // [lo...hi]
    private void sort(int[] nums, int lo, int hi) {
        // 单独一个元素 已经放在正确位置
        if (lo >= hi) {
            return;
        }

        // [lo...hi] 之间找一个数放在合适的位置 返回放置后的标
        int p = partition(nums, lo, hi);
        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }

    private int partition(int[] nums, int lo, int hi) {
        // 选择区间的第一个元素，作为本次放置的元素
        int pivot = nums[lo];
        int i = lo + 1, j = hi;
        while (i <= j) {
            //注意这里的开区间边界 否则会-1溢出
            while (i < hi && nums[i] <= pivot) {
                i++;
            }
            while (j > lo && nums[j] >= pivot) {
                j--;
            }

            // j=-1的情况 i=length的情况

            // 查出不进行交换
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }

        // 为什么是 j  跳出时情况如何
        // 拍好的情况一定是 j i 因为都有序了

        // j<lo的情况
        swap(nums, lo, j);

        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // 洗牌算法 将输入的数组随机打乱
    private void shuffle(int[] nums) {
        Random random = new Random();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            // 生成 [i,length-1]的随机数
            int r = i + random.nextInt(length - i);
            swap(nums, i, r);
        }
    }

    @Test
    public void test() {
        int[] nums = {5, 1, 1,2,4, 2, 0, 0};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}
    